UVa/10000 - Longest Paths/10000.2.cpp

   1 /*
   2   Time limit exceeded
   3  */
   4 #include <queue>
   5 #include <iostream>
   6 #include <vector>
   7
   8 using namespace std;
   9
  10 int n, end, length;
  11
  12 void dfs(int u, int w, vector<int> * g){
  13   if (w > length){
  14     length = w;
  15     end = u;
  16   }
  17   vector<int> &vecinos = g[u];
  18   for (int i=0; i<vecinos.size(); ++i){
  19     dfs(vecinos[i], w + 1, g);
  20   }
  21 }
  22
  23 int main(){
  24   int C = 1;
  25   while (cin >> n && n){
  26     int start;
  27     cin >> start, --start;
  28
  29     vector<int> g[n];
  30     int p, q;
  31     while (cin >> p >> q && (p+q)){
  32       --p, --q;
  33       g[p].push_back(q);
  34     }
  35     for (int i=0; i<n; ++i){
  36       sort(g[i].begin(), g[i].end());
  37     }
  38
  39     end = -1, length = -1;
  40     dfs(start, 0, g);
  41
  42     cout << "Case " << C++ << ": The longest path from " << start + 1 << " has length ";
  43     cout  << length << ", finishing at " << end + 1 << "." << endl << endl;
  44   }
  45   return 0;
  46 }